package oj;

public class Num236 {
    TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        //从根节点出发，找到lca（p和q出现在三个位置中的两个）
        find(root,p,q);
        return lca;
    }
    //在以root为根节点的二叉树中，是否能找到p或q。
    public boolean find(TreeNode root,TreeNode p,TreeNode q){
        if(root==null){
            return false;
        }
        //在左树中能找到p或者q
        int left=find(root.left,p,q)?1:0;
        //在右树中能找到p或者q
        int right=find(root.right,p,q)?1:0;
        //p/q是根节点
        int mid=(root==p || root==q)?1:0;
        //不包含p/q是根节点这种情况，left+right+mid==1，有两种情况
        //1.p/q同时在一棵树中找到，说明这个节点是p、q的公共祖先，但不是lca
        //2.p/q其中一个在一棵树中找到，说明这个节点是某一个节点的祖先，但不是公共祖先
        if(left+right+mid==2){
            //left+right+mid==2，说明p、q在三个位置中两个不同的位置出现，则这个节点就是p/q的lca
            lca=root;
            return true;
        }
        return (left+right+mid)>0;//find这个函数的语义就是传入根节点、p、q，看是否能找到p、q
        //因此只要(left+right+mid)>0，就说明在根节点下能找到p、q，只是不是lca
    }
}
